本篇文章的几个题目都可以看做是斐波那契问题。
斐波那契数列
题目
求斐波那契数列的第 n 项
解法1[Java]:
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) return n;
int pre2 = 0, pre1 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre2 + pre1;
pre2 = pre1;
pre1 = fib;
}
return fib;
}
}
时间复杂度为 ,空间复杂度为 。
解法2[Java]:打表
把每一步的结果计算出来,最后直接根据序号返回对应值。
优点:打出来的表可复用。缺点:空间复杂度为 。
跳台阶问题
这也看作一个斐波那契问题。
题目
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
解答1[Java]:
public class Solution {
public int JumpFloor(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 2; i < n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
}
从 开始,所以跳法可以分为两类
①第一下跳一级,这个时候剩下的跳法就是 ,
②第一下跳两级,这个时候剩下的跳法就是 ,
所以,。
注意:每一类跳法的总数是第一下的跳法乘以剩下的跳法,不是相加。
矩形覆盖问题
题目
我们可以用 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 的小矩形无重叠地覆盖一个 的大矩形,总共有多少种方法?
解答1[Java]:
public class Solution {
public int RectCover(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}
}
(2行8列)的矩形,
①最左边竖着放,右边变成 的问题。
②最左边横着放,要放两个,右边变成 的问题。
变态跳台阶问题
参考资料
- 对斐波那契问题分析的非常好的一篇文章:计算斐波纳契数,分析算法复杂度
- 斐波那契数列算法时间复杂度